package com.lw.leetcode.bingChaJi.c;

import java.util.HashSet;
import java.util.Set;

/**
 * Created with IntelliJ IDEA.
 * 1579. 保证图可完全遍历
 *
 * @author liw
 * @version 1.0
 * @date 2022/10/28 13:29
 */
public class MaxNumEdgesToRemove {

    public static void main(String[] args) {
        MaxNumEdgesToRemove test = new MaxNumEdgesToRemove();

        // 2
//        int[][] edges = {{3, 1, 2}, {3, 2, 3}, {1, 1, 3}, {1, 2, 4}, {1, 1, 2}, {2, 3, 4}};
//        int k = 4;

        // 0
//        int[][] edges = {{3, 1, 2}, {3, 2, 3}, {1, 1, 4}, {2, 1, 4}};
//        int k = 4;

        // -1
        int[][] edges = {{3, 2, 3}, {1, 1, 2}, {2, 3, 4}};
        int k = 4;

        int i = test.maxNumEdgesToRemove(k, edges);
        System.out.println(i);
    }

    public int maxNumEdgesToRemove(int n, int[][] edges) {
        int[] arr1 = new int[n + 1];
        for (int i = 0; i <= n; i++) {
            arr1[i] = i;
        }
        int y = 0;
        for (int[] edge : edges) {
            if (edge[0] == 3) {
                int a = find(arr1, edge[1]);
                int b = find(arr1, edge[2]);
                if (a == b) {
                    y++;
                } else {
                    arr1[b] = a;
                }
            }
        }
        Set<Integer> set = new HashSet<>();
        for (int i : arr1) {
            set.add(find(arr1, i));
        }
        int item = set.size();
        int count = 0;
        int[] arr2 = new int[n + 1];
        System.arraycopy(arr1, 0, arr2, 0, n + 1);
        for (int[] edge : edges) {
            if (edge[0] == 1) {
                int a = find(arr1, edge[2]);
                int b = find(arr1, edge[1]);
                if (a != b) {
                    arr1[b] = a;
                    item--;
                } else {
                    count++;
                }
            }
        }
        if (item > 2) {
            return -1;
        }
        item = set.size();
        for (int[] edge : edges) {
            if (edge[0] == 2) {
                int a = find(arr2, edge[2]);
                int b = find(arr2, edge[1]);
                if (a != b) {
                    arr2[b] = a;
                    item--;
                } else {
                    count++;
                }
            }
        }
        if (item > 2) {
            return -1;
        }
        return count + y;
    }

    private int find(int[] arr, int t) {
        if (arr[t] == t) {
            return t;
        }
        int v = find(arr, arr[t]);
        arr[t] = v;
        return v;
    }

}
